/*
2021-8-6
https://www.acwing.com/problem/content/1083/
*/
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;
const int N=35;
int f[N][N];
int l,r,k,b;

void init()
{
    for(int i=0;i<N;i++)
        for(int j=0;j<=i;j++)
            if(!j) f[i][j]=1;
            else f[i][j]=f[i-1][j-1]+f[i-1][j];
}

int dp(int n)
{
    if(!n) return 0;
    
    vector<int>nums;
    while(n) nums.push_back(n%b),n/=b;
    
    int res=0;
    int last=0;
    
    for(int i=nums.size()-1;i>=0;i--)
    {
        int x=nums[i];
        if(x)
        {
            res+=f[i][k-last];
            if(x>1)
            {
                if(k-last-1>=0) res+=f[i][k-last-1];
                break;
            }
            else
            {
                last++;
                if(last>k) break;
            }
        }
        if(!i && last==k) res++;
    }
    
    return res;
}

int main()
{
    init();
    cin>>l>>r>>k>>b;
    cout<<dp(r)-dp(l-1)<<endl;
    return 0;
}
